class Solution {
    // public void sortColors(int[] nums) {
    //     Arrays.sort(nums); // 不讲武德的写法
    // }

    // public void sortColors(int[] nums) {
    //     // 使用冒泡排序试试水(如果这个能过，基本上都能过了)
    //     for (int i = 0; i < nums.length; i++) {
    //         boolean flag = true;
    //         for (int j = 0; j < nums.length-1-i; j++) {
    //             if (nums[j] > nums[j+1]) {
    //                 int temp = nums[j];
    //                 nums[j] = nums[j+1];
    //                 nums[j+1] = temp;
    //                 flag = false;
    //             }
    //         }
    //         if (flag) {
    //             break;
    //         }
    //     }
    // }

    public void sortColors(int[] nums) {
        int len = nums.length;
        int left = -1; // 0区域
        int right = len; // 2区域
        for (int i = 0; i != right;) {
            int j = nums[i];
            // 判断当前位置是啥情况
            if (j == 0) {
                // 与left交换
                swap(nums, i++, ++left);
            } else if (j == 2) {
                // 与right交换
                swap(nums, i, --right); // i不能++，还未判断呢
            } else {
                i++;
            }
        }
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}